/*
 * convex_hull.cpp
 *
 *  Created on: 25.01.2013
 *      Author: Maksim Lazeba
 */
#include "convex_hull.h"
#include <algorithm>

struct points_comp {
	point_t& a;

	points_comp(point_t& p):a(p){}

	bool operator() (const point_t& b,const point_t& c)
	{
		int t = left_turn(a,b,c);
		if (t > 0)
			return true;
		if (t == 0)
			return b < c;
		return false;
	}
};

std::vector<point_t> get_convex_hull(std::vector<point_t>& points)
{

	std::size_t n = points.size();
	point_t p;
	int min_cur = 0;

	for (std::size_t i = 0; i < n; i++)
	{
		if (points[i] < points[min_cur])
			min_cur = i;
	}

	if (n < 2)
	{
		return points;
	}

	std::swap(points[0],points[min_cur]);
	points_comp comp(points[0]);
	std::sort(points.begin() + 1, points.end(), comp);

	if (n == 2)
	{
		return points;
	}

	std::vector<point_t> stack;

	stack.push_back(points[0]);
	stack.push_back(points[1]);

	for (auto i = points.begin() + 2; i < points.end(); i++)
	{
		int t = left_turn(stack[stack.size() - 2],stack[stack.size() - 1],*i);

		while (stack.size() > 2 && t <= 0)
		{
			stack.pop_back();
			t = left_turn(stack[stack.size() - 2],stack[stack.size() - 1],*i);
		}

		if (stack.size() == 2 && t == 0)
		{
			stack.pop_back();
		}

		stack.push_back(*i);
	}

	while (stack.size() > 2 && left_turn(stack[stack.size() - 2],stack[stack.size() - 1],points[0]) <= 0)
	{
		stack.pop_back();
	}


	if (stack.size() == 2 && stack[0] == stack[1])
	{
		stack.pop_back();
	}

	return stack;
}



